home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ietf / 92mar / rtgtbl-minutes-92mar.txt < prev    next >
Encoding:
Text File  |  1993-02-17  |  2.4 KB  |  53 lines
  1. This in only a rough draft - Megan 04/13/92
  2.  
  3. Minutes from the Routing Table Lookup BOF,
  4. Wednesday at 7:00
  5.  
  6. The purpose of the meeting was simply to discuss the various
  7. known approaches to software-driven routing table lookup algorithms.
  8. There is no intention to meet again, and no documentation is
  9. expected.  Presentations were given by the following:
  10.  
  11. Paul Tsuchiya         Cecilia Algorithm
  12. Joel Halpern        Patricia Algorithm
  13. Keith Sklower        Radix Algorithm (in Unix BSD)
  14. Rob Coltun        Binary Search Algorithm
  15. Fred Baker        16-wide Radix Algorithm
  16. Dino Farinacci        Hash Algorithm
  17.  
  18. Very briefly, Cecilia, Patricia, Sklower Radix, and 16-wide radix
  19. are all radix-type algorithms, meaning that they follow the search
  20. tree by branching according to the value of certain bits of the "key" 
  21. (the address being looked up).  The three former algorithms check
  22. one bit at a time, while the 16-wide checks 4 bits at a time.
  23. The three former algorithms can check bits in any order, while the
  24. 16-wide checks bits strictly MSB to LSB.
  25.  
  26. The Binary Search Algorithm does a greater than/less than compare
  27. to determine how to traverse the search tree.  The Hash Algorithm
  28. is not a tree-based search algorithm as the first 5 are, and won't
  29. be further discussed in these minutes.
  30.  
  31. Of the 6 algorithms, only Cecilia and Patricia handle non-contiguous
  32. masks efficiently (meaning, a tree of small size and depth).
  33. Sklower's Radix handles non-contiguous masks, but at the expense of
  34. a larger depth.  Cecilia has an efficient delete operation, whereas
  35. Patricia does not.  Patricia uses roughly 1/2 the memory of Cecilia.
  36. Note that in most router applications, a delete operation is not
  37. that important because routes don't appear and then disappear
  38. forever often.  Occasionally reforming the tree from scratch for the
  39. purpose of garbage collection suffices.  All of the algorithms can
  40. handle contiguous masks, but the hash algorithm performance decreases
  41. as the number of different sized masks increases.
  42.  
  43. Of the first 5 algorithms, only the Binary Search is balanced.
  44. However, note that this is only with respect to the number of elements
  45. in the tree, not with respect to the frequency with which each
  46. element is searched.  Usually the 16-wide Radix will have the
  47. smallest depth, because it covers 4 bits with a single compare
  48. rather than just 1.  However, since it goes strictly left to right,
  49. if the left bits do not differ in any of the routing table entries,
  50. the 16-wide Radix can be deeper than the first 4 algorithms.
  51.  
  52.  
  53.